\begin{abstract}
We study the fundamental problem of information spreading (also known
as gossip) in dynamically changing networks.  Such networks are
motivated by the rise of highly dynamic networks such as peer-to-peer
networks and ad hoc and mobile networks where the topology can change
rapidly with time.  In gossip, or more generally, $k$-gossip, there
are $k$ pieces of information (or tokens) that are initially present
in some nodes and the problem is to disseminate the $k$ tokens to all
nodes in as few rounds of distributed computation as possible,
assuming bandwidth constraints.  Studying the time complexity of
gossip is central to understanding the power of distributed
computation in dynamic networks as well to understanding the
fundamental algorithmic limitations and capabilities of various models
of dynamic networks.  Our focus is on token-forwarding algorithms,
which do not manipulate tokens in any way other than storing and
forwarding them.  A fundamental open problem is whether a linear (or
near-linear) time gossip algorithm is possible in general. This paper
presents several new results --- both lower and upper bounds --- on
gossip algorithms in dynamic networks under various adversarial models
and makes progress in resolving this open problem.

We first consider a worst-case adversarial model in which the
communication links for each round are chosen by an adaptive adversary
(that also knows the current token distribution and the random choices
made by the nodes), and nodes do not know who their neighbors for the
current round are before they broadcast their messages. Our first
result is an $\Omega(n + nk/\log n)$ lower bound on the number of
rounds needed for any token-forwarding (centralized or distributed)
algorithm to solve $k$-gossip, which resolves an open problem raised
in~\cite{kuhn+lo:dynamic}. Our lower bound applies to a wide class of
starting token distributions, including {\em well-mixed} ones in which
each node has each token independently with a constant probability.
Our result shows that one cannot obtain significantly efficient (i.e.,
$o(nk)$) token-forwarding algorithms for gossip in the above
worst-case adversarial model, thus motivating us to study weaker
models.

We next present two fast algorithms that can solve the gossip problem
in $O((n + k)\log^2 n)$ rounds with high probability, which is
essentially the best possible (up to polylogarithmic factors). Our
first algorithm is a distributed randomized algorithm that works for
any well-mixed distribution under an oblivious adversary (that has
full control of the network topology in each round, but is oblivious
to the random choices made by the algorithm).  A key ingredient of
this algorithm is an $O(\log n)$-bit protocol for sampling uniformly
at random from the symmetric difference of two sets stored at two
communicating nodes, a result that can be of independent interest in
communication complexity.  Our second algorithm is centralized, and
solves gossip for {\em every} starting distribution in $O((n +
k)\log^2 n)$ rounds for any dynamic network.
%Both of these results assume that each node can communicate
%simultaneously with each of its neighbors in each round.  We also
%present weaker upper bounds for the model where each node can only
%broadcast a single message to all of its neighbors in each round.
\end{abstract}

\junk{improving their lower bound of $\Omega(n \log k)$, and matching
  their upper bound of $O(nk)$ to within a logarithmic factor.  Our
  lower bound extends to centralized algorithms and also to randomized
  algorithms against an adversary that, in each round, knows the
  randomness used by the algorithm in that round. }

\junk{
  We present two polynomial-time centralized
%token-forwarding algorithms for $k$-gossip in this offline setting:
%(1) an $O(\min\{nk, n\sqrt{k \log n}\})$ round algorithm, and (2) an
%$(O(n^\eps), O(\log n))$ bicriteria approximation algorithm, for any
%$\eps > 0$, which means that our algorithm completes in $O(n^\eps)$
%times the optimal number of rounds and the number of tokens
%transmitted on any edge is $O(\log n)$ in each round.

%Our results are a step towards understanding the power
%and limitations of token-forwarding algorithms and our lower and upper
%bound techniques can be useful in addressing related problems in
%dynamic networks.
}
